package study.datastructure.link.leetcode;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
class Client23 {
    /**
     * 合并两个 合并多个 暴力
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;
        if (length==0) return null;


        ListNode result=null;
        for (ListNode list : lists) {
            result = mergeTwoLists2(list, result);
        }
        return result;
    }

    /**
     * 合并两个链表
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists2 (ListNode list1, ListNode list2){
        ListNode dHead = new ListNode(-1, null);
        ListNode p = dHead;
        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            //添加到新链表 添加较小值
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 == null) {
            p.next = p2;
        }
        if (p2 == null) {
            p.next = p1;
        }
        return dHead.next;
    }

    /**
     * 递归 分而治之
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists.length==0) {
            return null;
        }

       //数组抽成链表
        return split(lists,0,lists.length-1);

    }
    private ListNode split(ListNode[] lists,int i,int j){
        if (i==j){
            return lists[i];
        }

        int m=(i+j)>>>1;
        ListNode left=split(lists,i,m);
        ListNode right=split(lists,m+1,j);
        return mergeTwoLists2(left, right);
    }

    /**
     * 小顶堆 topK
     * @param lists
     * @return
     */

    public ListNode mergeKLists2(ListNode[] lists){
        if (lists==null) {
            return null;
        }

        MinHeapPriorityQueue minHeapPriorityQueue=new MinHeapPriorityQueue(lists.length);
        //向小顶堆添加元素
        for (ListNode listNode : lists) {
            if (listNode != null){
                minHeapPriorityQueue.insert(listNode);
            }
        }

        //新链表
        ListNode newNode=new ListNode(-1,null);
        ListNode p=newNode;

        //弹出最小值给新链表
        while (!minHeapPriorityQueue.isEmpty()) {
            ListNode min = minHeapPriorityQueue.poll();

            //添加到新链表
            p.next=min;
            p=p.next;

            //将最小元素的下一个添加到小顶堆
            if (min.next!=null){
                minHeapPriorityQueue.insert(min.next);
            }

        }
        return newNode.next;
    }
}